package edu.dayu.sort;

import java.util.Arrays;

/**
 * @author: dayu
 * @date: 2023/6/21 19:24
 * 快速排序
 * 快排就是选取一个基数，将右边的数全部比这个基数大，左边都比基数小。
 * 然后在数组分为左右两边重复第一个步骤。
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6,4,5,7,2,8,3,0,9,1};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int [] a,int began,int end){
        if (began>end)
            return;
        int i = began;
        int j = end;
        int temp = a[began];
        while (i<j){
            while(a[j]>=temp && j>i)
                j--;
            while (a[i]<=temp && j>i)
                i++;
            if (i<j) {
                int t = a[j];
                a[j] = a[i];
                a[i] = t;
            }
        }
        a[began] = a[i];
        a[i] = temp;
        System.out.println(Arrays.toString(a));
        sort(a,began,i-1);
        sort(a,i+1,end);
    }
}
